//https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
package codeRandomThoughts.Test17电话号码的字母组合;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    String[] letterMap = {
            "",//0
            "",//1
            "abc",//2
            "def",//3
            "ghi",//4
            "jkl",//5
            "mno",//6
            "pqrs",//7
            "tuv",//8
            "wxyz"//9
    };

    StringBuffer path = new StringBuffer();
    List<String> result = new ArrayList<>();


    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()){
            return result;
        }
        int index = 0;//记录遍历到了第几个数字
        backtracking(digits, index);
        return result;
    }

    public void backtracking(String digits, int index) {
        //终止条件
        if (index == digits.length()) {
            result.add(new String(path));
            return;
        }

        //单层递归逻辑
        //取数字对应的字符串
        String letters = letterMap[digits.charAt(index) - '0'];
        for (int i = 0; i < letters.length(); i++) {
            path.append(letters.charAt(i));
            backtracking(digits, index + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
